0% completed
Problem Statement
You are given a nestedList. Each element of the nestedList contains either integers or other such nested lists.
The depth level is determined by how many levels of nested lists the integer is within. For example, each element of the list [1, 1, [2], [2, [3]]] represents the depth of itself.
Return the sum of all integers of the list after multiplying each integer with its depth level.
Examples
-
Example 1:
- Input:
[[2, [3, 4]], [5, 6], 7] - Expected Output:
54 - Justification: The sum is calculated as 4 (2 at depth 2) + 9 (3 at depth 3) + 12 (4 at depth 3) + 10 (5 at depth 2) + 12 (6 at depth 2) + 7 (7 at depth 1).
- Input:
-
Example 2:
- Input:
[1, [4, [6]]] - Expected Output:
27 - Justification: The sum is 1 (depth 1) + 8 (4 at depth 2) + 18 (6 at depth 3).
- Input:
-
Example 3:
- Input:
[5, [2, [3, [4]]], 1] - Expected Output:
35 - Justification: The calculation is 5 (depth 1) + 4 (2 at depth 2) + 9 (3 at depth 3) + 16 (4 at depth 4) + 1 (depth 1).
- Input:
Solution
To solve this problem, a recursive approach is ideal. This approach works by traversing each element in the list. If the element is an integer, we multiply it by its depth and add it to the total sum. If the element is another list, we recursively process this list, increasing the depth by one.
This method is effective because it naturally handles the nested structure of the input and ensures that each integer is multiplied by its correct depth level. The recursion elegantly simplifies the process of diving into nested lists and accumulating the weighted sum.
Step-by-Step Algorithm
- Define a method
nestedSumwhich takes a nested list and an integerdepth. - Initialize a variable
totalSumto 0. - Iterate through each element in the nested list.
- If the element is an integer, add it to
totalSummultiplied bydepth. - If the element is a list, recursively call
nestedSumwith the list anddepth + 1, and add the result tototalSum.
- If the element is an integer, add it to
- Return
totalSum.
Algorithm Walkthrough
Let's consider the input: [[2, [3, 4]], [5, 6], 7].
- Start with the outer list:
[[2, [3, 4]], [5, 6], 7]withdepth = 1. - The first element is
[2, [3, 4]]. It's a nested list, so we process its elements:2is an integer atdepth = 2. Add2 * 2 = 4tototalSum.[3, 4]is another nested list. Process its elements atdepth = 3:3is an integer. Add3 * 3 = 9tototalSum.4is an integer. Add4 * 3 = 12tototalSum.
- The second element is
[5, 6], another list atdepth = 2. Process its elements:5is an integer. Add5 * 2 = 10tototalSum.6is an integer. Add6 * 2 = 12tototalSum.
- The third element is
7, a single integer atdepth = 1. Add7 * 1 = 7tototalSum. - Summing all these, the total sum is
4 + 9 + 12 + 10 + 12 + 7 = 54.
Code
Complexity Analysis
- Time Complexity:
O(N), where N is the total number of elements in the list, including nested lists. This is because each element is processed exactly once. - Space Complexity:
O(D), where D is the maximum depth of the nested lists. This is due to the recursive stack.
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis